package 递归.斐波那契数列.记忆法;

import java.util.Arrays;

public class Test {
    private static int f(int n, int[] a) {
        if (a[n] != -1) {
            return a[n];
        }
        a[n] = f(n - 1, a) + f(n - 2, a);
        return a[n];
    }

    public static int fibonacci(int n) {
        int[] a = new int[n + 1];
        Arrays.fill(a, -1);
        a[1] = 1;
//        a[2] = 1; 这里不能给2赋值, 如果n = 1, 则会报错
        a[0] = 0;
        return f(n, a);
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(1));
        System.out.println(fibonacci(2));
        System.out.println(fibonacci(3));
        System.out.println(fibonacci(4));
        System.out.println(fibonacci(5));
        System.out.println(fibonacci(6));
        System.out.println(fibonacci(7));
        System.out.println(fibonacci(8));
        System.out.println(fibonacci(9));
        System.out.println(fibonacci(10));
    }
}
